package club.babyf.nativeai.demo.algorithm;

/**
 * _26_FindMedianSortedArrays.
 *
 * @author zhanglei.
 * @date 2025/7/26 08:55.
 * @description 寻找两个正序数组的中位数.
 */
public class _26_FindMedianSortedArrays {

    /**
     * 寻找两个正序数组的中位数
     *
     * @param nums1 数组1
     * @param nums2 数组2
     * @return 中位数
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 计算两个数组的总长度
        int len = nums1.length + nums2.length;

        // 计算中位数的两个位置（应对奇偶两种情况）：
        // 当总长度为奇数时，k1 和 k2 会相等
        // 当总长度为偶数时，k1 和 k2 会相邻（如长度为4时，k1=2, k2=3）
        int k1 = (len + 1) / 2;  // 第一个中位数位置
        int k2 = (len + 2) / 2;  // 第二个中位数位置

        // 在两个有序数组中查找第k1小的元素
        int result1 = findKth(nums1, nums2, k1);
        // 在两个有序数组中查找第k2小的元素
        int result2 = findKth(nums1, nums2, k2);

        // 计算中位数：如果是奇数，result1和result2相同；如果是偶数，取平均值
        return (result1 + result2) / 2.0;  // 使用2.0确保结果是浮点数
    }

    /**
     * 辅助函数：在两个有序数组中查找第k小的元素
     *
     * @param nums1 数组1
     * @param nums2 数组2
     * @param k     中间位置
     * @return 中间位置的值
     */
    private static int findKth(int[] nums1, int[] nums2, int k) {
        // 初始化两个数组的起始位置
        int start1 = 0;  // nums1的当前查找起始位置
        int start2 = 0;  // nums2的当前查找起始位置

        // 获取两个数组的长度
        int len1 = nums1.length;
        int len2 = nums2.length;

        // 使用无限循环，通过内部条件返回结果
        while (true) {
            // 情况1：nums1数组已全部排除
            if (start1 == len1) {
                // 直接在nums2中取剩余部分的第k个元素
                return nums2[start2 + k - 1];
            }
            // 情况2：nums2数组已全部排除
            if (start2 == len2) {
                // 直接在nums1中取剩余部分的第k个元素
                return nums1[start1 + k - 1];
            }
            // 情况3：当k缩减为1时
            if (k == 1) {
                // 比较两个数组当前起始位置的元素，返回较小的那个
                return Math.min(nums1[start1], nums2[start2]);
            }

            // 计算本次要比较的位置：取k/2，但要考虑数组边界
            int half = k / 2;  // 本次计划比较的元素数量

            // 计算nums1中要比较的位置（防止数组越界）：
            // 从start1开始，取half个元素后的位置，但不能超过数组末尾
            int index1 = Math.min(start1 + half, len1) - 1;

            // 计算nums2中要比较的位置（同样防止越界）
            int index2 = Math.min(start2 + half, len2) - 1;

            // 比较两个数组在计算位置的值
            if (nums1[index1] <= nums2[index2]) {
                // 排除nums1中start1到index1之间的元素
                k -= (index1 - start1 + 1);  // 更新k值：减去排除的元素数量
                start1 = index1 + 1;         // 更新nums1的起始位置
            } else {
                // 排除nums2中start2到index2之间的元素
                k -= (index2 - start2 + 1);  // 更新k值：减去排除的元素数量
                start2 = index2 + 1;         // 更新nums2的起始位置
            }
            // 循环继续，使用更新后的start1/start2和k值进行下一轮查找
        }
    }

    public static void main(String[] args) {
        int[] arr1 = new int[] {1, 3};
        int[] arr2 = new int[] {2};
        double d1 = findMedianSortedArrays(arr1, arr2);
        System.out.println(d1);

        arr1 = new int[] {1, 2};
        arr2 = new int[] {3, 4};
        d1 = findMedianSortedArrays(arr1, arr2);
        System.out.println(d1);

        arr1 = new int[] {5};
        arr2 = new int[] {1, 2, 3, 4, 6, 7, 8, 9, 10};
        d1 = findMedianSortedArrays(arr1, arr2);
        System.out.println(d1);

    }

}
